package willis.sword.offer.algorithm.binarytree;


import lombok.Data;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 二叉树
 */
@Data
public class BinaryTreeTest {


    public static Node restructureTree(int[] front, int[] middle) {
        if (front.length == 0 || middle.length == 0) {
            return null;
        }
        Node root = new Node(front[0]);
        int middleRootIndex = 0;
        //查找中序遍历根节点的index
        for (int i = 0; i < middle.length; i++) {
            if (middle[i] == front[0]) {
                middleRootIndex = i;
                break;
            }
        }
        //左子树的中序遍历
        int[] leftMiddleTree = Arrays.copyOfRange(middle, 0, middleRootIndex);
        //右子树的中序遍历
        int[] rightMiddleTree = Arrays.copyOfRange(middle, middleRootIndex + 1, middle.length);
        //左子树的前序遍历
        int[] leftFrontTree = Arrays.copyOfRange(front, 1, leftMiddleTree.length + 1);
        //右子树的前序遍历
        int[] rightFrontTree = Arrays.copyOfRange(front, leftMiddleTree.length + 1, front.length);
        root.setLeft(restructureTree(leftFrontTree, leftMiddleTree));
        root.setRight(restructureTree(rightFrontTree, rightMiddleTree));
        return root;

    }

    public static List<Integer> preOrderTraversal(Node root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }

    public static void helper(Node root, List<Integer> res) {
        if (root != null) {
            res.add(root.root);
            if (root.left != null) {
                helper(root.left, res);
            }
            if (root.right != null) {
                helper(root.right, res);
            }
        }
    }

    public static void main(String[] args) {

        int[] front = new int[]{1, 2, 4, 7, 3, 5, 6, 8};
        int[] middle = new int[]{4, 7, 2, 1, 5, 3, 8, 6};

        Node node = restructureTree(front, middle);

        System.out.println(node);
        List<Integer> integers = preOrderTraversal(node);
        System.out.println(integers);
    }


    @Data
    static
    class Node {

        private int root;

        private Node left;

        private Node right;

        public Node() {
        }


        public Node(int root) {
            this.root = root;
        }
    }


}
